package q572_isSubtree;

import CommonClass.Common.TreeNode;

public class Solution {

    /*
    判断root中是否有subRoot这个子树
    采用回溯的方式
     */
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if (root == null) {
            return false;
        }

        // 当发现当前节点和subRoot节点的值相同时 使用isSame判断是否为一样的树
        if (root.val == subRoot.val) {
            if (isSame(root, subRoot)) return true;
        }

        // 否则就去root的两端继续找是否存在子树
        return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
    }

    // 判断是否为一样的树
    private boolean isSame(TreeNode root, TreeNode subRoot) {
        if (root == null && subRoot == null) {
            return true;
        }

        if (root == null || subRoot == null) {
            return false;
        }

        return root.val == subRoot.val && isSame(root.left, subRoot.left) && isSame(root.right, subRoot.right);
    }
}
